package com.gaogzhen.algorithms4.foundation;

/**
 *  quick-union算法
 */
public class QuickUnionUF extends AbstractUnionFind{

    /**
     * 初始化有n个触点的parent[]
     *
     * @param  n the number of element
     */
    public QuickUnionUF(int n) {
        super(n);
    }

    /**
     * 返回触点p所在的分量标志
     *
     * @param  p 触点p
     */
    public int find(int p) {
        validate(p);
        while (p != getId(p))
            p = getId(p);
        return p;
    }

    /**
     * 合并触点p所在分量和触点q所在分量
     *
     * @param  p 触点或者所在分量
     * @param  q 触点q所在分量
     */
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return;
        setId(rootP, rootQ);
        decreaseCount();
    }
}